package 剑指offer.树;

import java.util.LinkedList;

/**
 * 请实现两个函数，分别用来序列化和反序列化二叉树
 */
public class 第37题序列化二叉树 {


    public static class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
        TreeNode center = null;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    /*
    通过 LDR 和 DLR 可以恢复一棵二叉树
    序列化成 DLR 可以便于反序列化，因为第一个节点就是根节点。
    反序列化的时候可以根据读出的每个节点构建树
     */

//    StringBuffer buffer = new StringBuffer();
//
//    String Serialize(TreeNode root) {
//        if (root == null) {
//            buffer.append("#,");
//            return buffer.toString();
//        }
//        buffer.append(root.val + ",");
//        Serialize(root.left);
//        Serialize(root.right);
//        return buffer.toString();
//    }
//
//    int i = -1;
//
//    // 注意指针的指向
//    TreeNode Deserialize(String str) {
//        i++;
//        TreeNode root = null;
//        if (str == null || str.length() == 0)
//            return root;
//        String[] nodes = str.split(",");
//        if (!nodes[i].equals("#")) {
//            root = new TreeNode(Integer.valueOf(nodes[i]));
//            // 恢复先序遍历的结果的时候也要先从左孩子开始
//            root.left = Deserialize(str);
//            root.right = Deserialize(str);
//        }
//        return root;
//    }


    /********* 层序遍历 *************/
    public static String serialize(TreeNode root) {
        if (null == root) {
            return "";
        }
        // 使用队列存储下一层节点
        LinkedList<TreeNode> queue = new LinkedList<>();
        StringBuilder builder = new StringBuilder();
        queue.add(root);
        while (!queue.isEmpty()) {
            // 处理每一个节点的时候，都要把该节点的子节点放入队尾，等待下一次被取出读取
            TreeNode node = queue.removeFirst();
            if (node != null) {
                builder.append(node.val);
                queue.addLast(node.left);
                queue.addLast(node.center);
                queue.addLast(node.right);
            } else {
                builder.append("#");
            }
            builder.append(",");
        }
        // 去掉最后一个 , 号
        builder.deleteCharAt(builder.length() - 1);
        return builder.toString();
    }

    public static TreeNode deserialize(String data) {
        if (null == data || data.isEmpty()) {
            return null;
        }
        String[] nodes = data.split(",");
        int index = 0;
        TreeNode root = buildNode(nodes[index++]);
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.removeFirst();
            node.left = buildNode(nodes[index++]);
            node.center = buildNode(nodes[index++]);
            node.right = buildNode(nodes[index++]);
            if (node.left != null) {
                queue.addLast(node.left);
            }
            if (node.center != null) {
                queue.addLast(node.left);
            }
            if (node.right != null) {
                queue.addLast(node.right);
            }
        }
        return root;
    }

    private static TreeNode buildNode(String node) {
        if ("#".equals(node)) {
            return null;
        }
        return new TreeNode(Integer.valueOf(node));
    }

    public static void main(String[] args) {
        TreeNode n1 = new TreeNode(1);
        TreeNode n2 = new TreeNode(2);
        TreeNode n3 = new TreeNode(3);
        TreeNode n4 = new TreeNode(4);
        TreeNode n5 = new TreeNode(5);
        TreeNode n6 = new TreeNode(6);
        n1.left = n2;
        n1.right = n3;
        n1.center = n5;
        n3.left = n4;
        n3.right = n6;
        String ans = serialize(n1);
        System.out.println(ans);

        TreeNode root = deserialize(ans);
    }
}
